package com.example.demo.zaqizabatest.leetcode.day2;

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/


import java.util.*;

/**
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
 * 每个节点除了有一个 next 指针指向下一个节点，
 * 还有一个 random 指针指向链表中的任意节点或者 null。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution3 {
    public static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        List<Integer> list = new ArrayList<>();
        List<Node> nodes = new ArrayList<>();
        list.add(head.val);
        nodes.add(head);
        Node nextNode = head.next;
        while (nextNode != null) {
            nodes.add(nextNode);
            list.add(nextNode.val);
            nextNode = nextNode.next;

        }
        List<Map<Integer, Integer>> randomFlags = new ArrayList<>();
        for (int i = 0; i < nodes.size(); i++){
            Map<Integer, Integer> flag = new HashMap<>();
            if (nodes.get(i).random == null){
                flag.put(i, null);
                randomFlags.add(flag);
                continue;
            }
            for (int j = 0; j < nodes.size(); j++){
                if (nodes.get(i).random == nodes.get(j)){
                    flag.put(i, j);
                    randomFlags.add(flag);
                    break;
                }
            }
        }
        List<Node> newNodes = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            newNodes.add(new Node(list.get(i)));
        }
        for (int i = 0; i < newNodes.size() - 1; i++) {
            newNodes.get(i).next = newNodes.get(i + 1);
            Integer flag = randomFlags.get(i).get(i);
            if (flag != null){
                newNodes.get(i).random = newNodes.get(flag);
            }
        }
        Integer lastFlag = randomFlags.get(list.size() - 1).get(list.size() - 1);
        if (lastFlag != null) {
            newNodes.get(list.size() -1).random = newNodes.get(lastFlag);
        }
        return newNodes.get(0);




    }

    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static void main(String[] args) {

        Node node1 = new Node(7);
        Node node2 = new Node(13);
        Node node3 = new Node(11);
        Node node4 = new Node(10);
        Node node5 = new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node2.random = node1;
        node3.random = node5;
        node4.random = node3;
        node5.random = node1;
        copyRandomList(node1);
    }
}
